package array;

/**
 * A peak element is an element that is greater than its neighbors.
 * Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.
 * The array may contain multiple peaks, in that case return 
 * the index to any one of the peaks is fine.
 * You may imagine that num[-1] = num[n] = -∞.
 * For example, in array [1, 2, 3, 1], 3 is a peak element and 
 * your function should return the index number 2.
 * click to show spoilers.
 * 
 * Note:
 * Your solution should be in logarithmic complexity.
 *
 */
public class FindPeakElement {
	public int findPeakElement(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            int mid = nums[m];
            if ((m == 0 || nums[m - 1] < mid) && (m == nums.length - 1 || nums[m + 1] < mid)) return m;
            if (m > 0 && nums[m - 1] > mid) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return -1;
    }
    
    public int findPeakElementNaive(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if ((i == 0 || nums[i] > nums[i - 1]) && (i == nums.length - 1 || nums[i] > nums[i + 1]))
                return i;
        }    
        return -1;
    }
}
